package com.wuzihao.maze.service.impl;

import com.wuzihao.maze.constant.BlockStatus;
import com.wuzihao.maze.constant.Direction;
import com.wuzihao.maze.constant.VisitStatus;
import com.wuzihao.maze.service.GenerateMazeStrategy;

import java.awt.Point;
import java.util.Random;
import java.util.Stack;

/**
 * DFS算法生成迷宫地图
 * 
 * @author gonggy
 */
public class DFSGenerateStrategy implements GenerateMazeStrategy {

	private int[][] map;// 地图数组
	private int size;// 迷宫尺寸

	/**
	 * 初始化迷宫数组
	 */
	private void init() {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				map[i][j] = BlockStatus.INIT;
			}
		}
	}

	@Override
	public int[][] generate(int size) {
		this.size = size;
		map = new int[size][size];
		init();

		Stack<Point> stack = new Stack<>();// 用于生成迷宫时的栈
		Direction direction;
		map[1][1] = BlockStatus.OPEN;// 初始点
		stack.push(new Point(1, 1));// 将当前点压入栈中
		VisitStatus visitStatus = new VisitStatus();// 标记某方向是否走过
		int n = 0;// 标记某方向是否有未访问节点
		Random rand = new Random();

		while (!stack.isEmpty()) {
			direction = Direction.valueOf(rand.nextInt(4));
			n = 0;
			if (direction == Direction.UP) {// up
				//peek返回栈顶元素
				if (!isVisted(stack.peek().x - 2, stack.peek().y)) {
					// 标记该点的邻居节点，打开之间的墙，并把邻居节点压入栈中
					map[stack.peek().x - 1][stack.peek().y] = BlockStatus.OPEN;
					map[stack.peek().x - 2][stack.peek().y] = BlockStatus.OPEN;
					stack.push(new Point(stack.peek().x - 2, stack.peek().y));
					n++;
				}
				visitStatus.up = true;// 标记该方向已走过
			} else if (direction == Direction.DOWN) {// down
				if (!isVisted(stack.peek().x + 2, stack.peek().y)) {
					map[stack.peek().x + 1][stack.peek().y] = BlockStatus.OPEN;
					map[stack.peek().x + 2][stack.peek().y] = BlockStatus.OPEN;
					stack.push(new Point(stack.peek().x + 2, stack.peek().y));
					n++;
				}
				visitStatus.down = true;
			} else if (direction == Direction.LEFT) {// left
				if (!isVisted(stack.peek().x, stack.peek().y - 2)) {
					map[stack.peek().x][stack.peek().y - 1] = BlockStatus.OPEN;
					map[stack.peek().x][stack.peek().y - 2] = BlockStatus.OPEN;
					stack.push(new Point(stack.peek().x, stack.peek().y - 2));
					n++;
				}
				visitStatus.left = true;
			} else if (direction == Direction.RIGHT) {// right
				if (!isVisted(stack.peek().x, stack.peek().y + 2)) {
					map[stack.peek().x][stack.peek().y + 1] = BlockStatus.OPEN;
					map[stack.peek().x][stack.peek().y + 2] = BlockStatus.OPEN;
					stack.push(new Point(stack.peek().x, stack.peek().y + 2));
					n++;
				}
				visitStatus.right = true;
			}

			if (n == 0) {
				if (visitStatus.isAllVisited()) {// 如果四个方向都走过且没有未访问的节点，则退回上一个节点
					stack.pop();
					visitStatus.reset();
				}
			} else {
				visitStatus.reset();
			}
		}
		return map;
	}

	// 判断该点是否存在并访问过
	private boolean isVisted(int x, int y) {
		if ((x > 0 && x < size) && (y > 0 && y < size) && map[x][y] == BlockStatus.INIT) {
			return false;
		}
		return true;
	}

}
